package Top_Interview_Questions.Bit_Manipulation;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/30 20:34
 * <p>
 * #.递归+回溯的套路
 * https://leetcode-cn.com/problems/subsets/solution
 * /xiang-xi-jie-shao-di-gui-hui-su-de-tao-lu-by-reedf/
 *
 * #.递归和回溯的多题型
 * https://leetcode-cn.com/problems/subsets/solution/hui-su-suan-fa-by-powcai-5/
 */
public class _0078 {

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        _0078 test = new _0078();
        System.out.println(test.subsets(nums));
    }






    /**
     *  这个回溯写的不太标准,复习的时候自己写个
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0, nums, res, new ArrayList<Integer>());
        return res;
    }

    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
        res.add(new ArrayList<>(tmp));
        for (int j = i; j < nums.length; j++) {
            tmp.add(nums[j]);
            backtrack(j + 1, nums, res, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }

}
